//矩阵中的最长递增路径
//测试链接：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
public class LongestIncreasingPath {
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    int[][] memo;
    int m,n;
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length; n = matrix[0].length;
        memo = new int[m][n];

        int max = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int path = dfs(matrix, i, j);
                max = Math.max(max, path);
            }
        }
        return max;
    }

    public int dfs(int[][] matrix, int i, int j) {
        if(memo[i][j] != 0) return memo[i][j];

        int ans = 1;
        for(int k = 0; k < 4; k++) {
            int x = dx[k] + i, y = dy[k] + j;
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                int temp = dfs(matrix,x,y)+1;
                ans = Math.max(temp,ans);
            }
        }
        memo[i][j] = ans;
        return ans;
    }
}
